İşte Eratosten Kalburu hakkında kapsamlı bir makale:
Eratosten Kalburu
Eratosten Kalburu, belirli bir sınıra kadar olan tüm asal sayıları bulmak için kullanılan basit ve eski bir algoritmadır. Adını, MÖ 3. yüzyılda yaşamış Yunan matematikçi Eratosten'den almıştır. Verimli ve anlaşılması kolay olması nedeniyle hala sıklıkla öğretilmektedir.
İçindekiler
-
-
-
1. Giriş
Eratosten Kalburu, bir aralıktaki asal sayıları bulmanın en basit ve eski yöntemlerinden biridir. Temel prensibi, asal sayı'nın katlarını eleyerek ilerlemektir. Bu işlem, belirli bir sınıra kadar olan tüm asal sayılar belirlenene kadar devam eder.
2. Tarihçe
Algoritma, MÖ 3. yüzyılda yaşamış olan Yunan matematikçi Eratosten tarafından geliştirilmiştir. Eratosten, aynı zamanda Dünya'nın çevresini oldukça doğru bir şekilde hesaplamasıyla da bilinir.
3. Algoritma
Adım Adım Açıklama
- Belirli bir n sayısına kadar olan tüm sayıların (2'den n'ye kadar) bir listesini oluşturun.
- Listenin ilk sayısı olan 2 ile başlayın (2 bir asal sayı'dır).
- 2'nin tüm katlarını (4, 6, 8, ...) listeden eleyin.
- Listede işaretlenmemiş bir sonraki sayıya gidin (bu sayı da bir asal sayı'dır).
- Bu sayının tüm katlarını listeden eleyin.
- Listede işaretlenmemiş bir sonraki sayıya gidin ve 4. ve 5. adımları tekrarlayın.
- Listenin sonuna kadar bu işlemi tekrarlayın.
- Listenin sonunda kalan işaretlenmemiş sayılar, n'ye kadar olan tüm asal sayılardır.
Sözde Kod
function eratostenKalburu(n) {
// n boyutunda bir boolean dizisi oluştur (başlangıçta hepsi true)
asalMi = new boolean[n+1];
doldur(asalMi, true); // Tüm elemanları true yap
asalMi[0] = asalMi[1] = false; // 0 ve 1 asal sayı değildir
for (p = 2; p*p <= n; p++) {
// Eğer asalMi[p] hala true ise, bu bir asal sayıdır
if (asalMi[p] == true) {
// p'nin tüm katlarını işaretle
for (i = p*p; i <= n; i += p)
asalMi[i] = false;
}
}
// Tüm asal sayıları yazdır
for (p = 2; p <= n; p++) {
if (asalMi[p] == true)
yazdır(p);
}
}
4. Karmaşıklık Analizi
Zaman Karmaşıklığı
Eratosten Kalburu'nun zaman karmaşıklığı O(n log log n)'dir. Bu, algoritmanın çok verimli olduğu anlamına gelir. Algoritmanın asal sayıları bulma hızı, aralığın büyüklüğü arttıkça nispeten yavaş bir şekilde artar.
Alan Karmaşıklığı
Eratosten Kalburu'nun alan karmaşıklığı O(n)'dir, çünkü n'ye kadar olan tüm sayılar için bir dizi saklamayı gerektirir.
5. Optimizasyonlar
- Sadece Tek Sayıları Kontrol Etme: 2'den sonra, tüm çift sayılar asal sayı olamaz. Bu nedenle, 2'den sonra sadece tek sayıları kontrol ederek algoritmayı optimize edebiliriz.
- Karekök Sınırı: Bir sayının katlarını işaretlemeye, sayının karesinden başlayarak başlayabiliriz (örneğin, 7 için 49'dan başlayarak). Çünkü daha küçük katlar zaten daha küçük asal sayılar tarafından işaretlenmiş olacaktır.
6. Uygulamalar
Eratosten Kalburu çeşitli uygulamalarda kullanılır:
- Kriptografi: Asal sayılar, kriptografi'de önemli bir rol oynar.
- Sayı Teorisi: Asal sayılarla ilgili birçok problemde kullanılır.
- Bilgisayar Bilimi: Çeşitli algoritmaların test edilmesinde ve geliştirilmesinde kullanılır.
7. Avantajlar ve Dezavantajlar
Avantajları
- Basit ve kolay anlaşılır bir algoritmadır.
- Verimli bir algoritmadır (O(n log log n) zaman karmaşıklığı).
- Belirli bir sınıra kadar olan tüm asal sayıları bulmak için etkilidir.
Dezavantajları
- Büyük n değerleri için hafıza gereksinimi yüksek olabilir (O(n) alan karmaşıklığı).
- Çok büyük sayılar için diğer algoritmalar daha verimli olabilir.
8. Alternatif Algoritmalar
- Atkin Kalburu: Eratosten Kalburu'na göre daha karmaşık, ancak bazı durumlarda daha verimli bir alternatiftir.
- Probabilistic Asallık Testleri: Örneğin, Miller-Rabin Asallık Testi. Bu testler, bir sayının asal sayı olup olmadığını belirli bir olasılıkla belirler.
9. Ayrıca Bakınız
10. Referanslar
- Crandall, R., & Pomerance, C. (2005). Prime Numbers: A Computational Perspective (2nd ed.). Springer.
- Knuth, D. E. (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley.
Umarım bu makale Eratosten Kalburu hakkında kapsamlı bilgi sağlamıştır.